1. Field of the Invention
The present invention relates to a method of and an apparatus for multiplying matrix data in discrete cosine transform (DCT) or inverse discrete cosine transform (IDCT) for use in the compression of image data or the like.
2. Description of the Prior Art
It has been proposed by the inventor of the present application to reduce the amount of matrix computation for a two-dimensional 8.times.8 DCT and a two-dimensional 8.times.8 IDCT through a suitable matrix resolution, in U.S. Ser. No. 020313 filed Feb. 19, 1993 on apparatus for discrete cosine transform and apparatus for inverse discrete cosine transform.
More specifically, a two-dimensional 8.times.8 DCT is a transform from the 64 elements of an 8.times.8 matrix in a real space into the 64 elements of an 8.times.8 matrix in a frequency space. If it is assumed that the 64 elements of the 8.times.8 matrix in the real space are regarded as a vertical vector (a vector composed of 64 elements: Xc) and the 64 elements of the 8.times.8 matrix in the frequency space are also regarded as a vertical vector (a vector composed of 64 elements: Yc), then the two-dimensional 8.times.8 DCT becomes a linear transform from the vector Xc into the vector Yc.
Thus, EQU Yc!=M! Xc!
where M! is a 64.times.64 constant matrix.
In the above earlier application, it has been proposed to reduce the amount of computation based on the fact that the 64.times.64 constant matrix M! can be resolved into: EQU M!=W! V! TS! R! L! Q!/8
where Q!, L!, R!, TS!, V!, and W! are 64.times.64 constant matrices, respectively. The details of these matrices are shown in FIGS. 1 through 6 of the accompanying drawings.
FIG. 1 shows the elements of the 64.times.64 constant matrix Q!. FIG. 2 shows the elements of the 64.times.64 constant matrix L!. FIG. 3 shows the elements of the 64.times.64 constant matrix R!. FIG. 4 shows the elements of the 64.times.64 constant matrix TS!. FIG. 5 shows the elements of the 64.times.64 constant matrix V!. FIG. 6 shows the elements of the 64.times.64 constant matrix W!.
In FIGS. 1 through 6, the blanks represent 0, the symbol + represents +1, the symbol - represents -1, and the alphabetical letters are defined as follows:
a=-e=cos (.pi./16) PA1 b=-f=cos (3.pi./16) PA1 c=-g=cos (5.pi./16) PA1 d=-h=cos (7.pi./16) PA1 i=-j=cos (4.pi./16) PA1 k=-m=cos (2.pi./16) PA1 l=-n=cos (6.pi./16).
While the blanks represent 0, some 0s that are required to give an easier understanding of the position of +1 and -1 are illustrated.
Specifically, in the above earlier application, a permutation circuit calculates the constant matrix Q!, a four-order inner product calculating circuit with coefficients +1 and -1 calculates the constant matrix L!, a permutation circuit calculates the constant matrix R!, an eight-order inner product calculating circuit with coefficients 0, +1, and -1 calculates the constant matrix TS!, a four-order inner product calculating circuit calculates the constant matrix V!, and a permutation circuit calculates the constant matrix W!. These circuits make up a circuit arrangement for computing a two-dimensional 8.times.8 DCT.
Such a circuit arrangement is shown in FIG. 7 of the accompanying drawings. In FIG. 7, data in eight rows and eight columns are inputted as the vector Xc! shown in FIG. 8 of the accompanying drawings in the order of columns from an input terminal IN, and supplied through a first 64-word permutation circuit 41 to a first four-order inner product calculating circuit 42. The first four-order inner product calculating circuit 42 supplies an output signal through a second 64-word permutation circuit 43 to a second eight-degree inner product calculating circuit 44. The second eight-order inner product calculating circuit 44 supplies an output signal to a third four-order inner product calculating circuit 45, whose output signal is supplied through a third 64-word permutation circuit 46 to an output terminal OUT.
The first inner product calculating circuit 42 has only coefficients +1 and -1, and the second inner product calculating circuit 44 has only coefficients 0, +1, and -1. The third inner product calculating circuit 45 has coefficients whose values are inherent in DCT.
A two-dimensional 8.times.8 IDCT is a transform from the 64 elements of an 8.times.8 matrix in a frequency space into the 64 elements of an 8.times.8 matrix in a real space. If it is assumed that the 64 elements of the 8.times.8 matrix in the frequency space are regarded as a vertical vector (a vector composed of 64 elements: Yc) and the 64 elements of the 8.times.8 matrix in the real space are also regarded as a vertical vector (a vector composed of 64 elements: Xc), then the two-dimensional 8.times.8 IDCT becomes a linear transform from the vector Yc into the vector Xc.
Thus, EQU Xc!=IM! Yc!
where IM! is a 64.times.64 constant matrix.
In the above earlier application, it has been proposed to reduce the amount of computation based on the fact that the 64.times.64 constant matrix IM! can be resolved into: EQU IM!=t Q! t L! t R! t TS! t V! t W!/8
where t Q! is a transposed matrix of the 64.times.64 constant matrix Q!, t R! is a transposed matrix of the 64.times.64 constant matrix R!, t TS! is a transposed matrix of the 64.times.64 constant matrix TS!, t V! is a transposed matrix of the 64.times.64 constant matrix V!, and t W! is a transposed matrix of the 64.times.64 constant matrix W!.
Specifically, in the above earlier application, a permutation circuit calculates the constant matrix t W!, a four-order inner product calculating circuit calculates the constant matrix t V!, an eight-order inner product calculating circuit with coefficients 0, +1, and -1 calculates the constant matrix t TS!, a permutation circuit calculates the constant matrix t R!, a four-order inner product calculating circuit with coefficients +1 and -1 calculates the constant matrix t L!, and a permutation circuit calculates the constant matrix t Q!. These circuits make up a circuit arrangement for computing a two-dimensional 8.times.8 IDCT.
Such a circuit arrangement is shown in FIG. 9 of the accompanying drawings. In FIG. 9, data in eight rows and eight columns from an input terminal IN are supplied through a fourth 64-word permutation circuit 71 to a fourth four-order inner product calculating circuit 72. The fourth four-order inner product calculating circuit 72 supplies an output signal to a fifth eight-order inner product calculating circuit 73. The fifth eight-order inner product calculating circuit 73 supplies an output signal through a fifth 64-word permutation circuit 74 to a sixth four-order inner product calculating circuit 75, whose output signal is supplied through a sixth 64-word permutation circuit 76 to an output terminal OUT.
The calculation of the constant matrix TS! is a computation of: ##EQU1## from an inputted vertical vector A! composed of 64 elements Ai! to output a vertical vector B! composed of 64 elements Bi!.
The above calculation is carried out in the eight-order inner product calculating circuit 44. Since the eight-order inner product calculation is effected on each of the 64 data items, it is necessary to carry out a total of 64.times.8=512 additions and subtractions.
The calculation of the constant matrix t TS! is a computation of: ##EQU2## from an inputted vertical vector C! composed of 64 elements Ci! to output a vertical vector D! composed of 64 elements Di!.
The above calculation is carried out in the eight-order inner product calculating circuit 73. Since the eight-order inner product calculation is effected on each of the 64 data items, it is necessary to carry out a total of 64.times.8=512 additions and subtractions.
Furthermore, the calculation of the constant matrix L! is a computation of: ##EQU3## from an inputted vertical vector E! composed of 64 elements Ei! to output a vertical vector F! composed of 64 elements Fi!.
The above calculation is carried out in the four-order inner product calculating circuit 42. Since the four-degree inner product calculation is effected on each of the 64 data items, it is necessary to carry out a total of 64.times.4=256 additions and subtractions.
The problems with the earlier application are that the amount of computation is excessively large for calculating each of the constant matrices TS!, t TS!, for example, as 512 additions and subtractions have to be made, and also the amount of computation is excessively large for calculating the constant matrix L!, for example, as 256 additions and subtractions have to be made,